package main

import (
	"fmt"
)

/*
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
并返回其长度。如果不存在符合条件的子数组，返回 0 。



示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
*/

//暴力
/*
枚举数组 nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标j，
使得从 nums[i] 到 nums[j] 的元素和大于或等于 target，并更新子数组的最小长度（此时子数组的长度是 j-i+1）。
*/
func minSubArrayLen1(target int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := 10000000
	for i := 0; i < n; i++ {
		sum := 0
		for j := i; j < n; j++ {
			sum += nums[j]
			if sum >= target { //如果要相等，改成==即可
				ans = min(ans, j-i+1)
				break
			}
		}
	}
	if ans == 10000000 {
		return 0
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

//滑动窗口
func minSubArrayLen2(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := 1000000
	start, end := 0, 0
	sum := 0
	for end < n {
		sum += nums[end]
		for sum >= s {
			ans = min(ans, end-start+1)
			sum -= nums[start]
			start++
		}
		end++
	}
	if ans == 1000000 {
		return 0
	}
	return ans
}

func main() {
	n := []int{2, 3, 1, 2, 4, 3, 0, 2}
	fmt.Println(minSubArrayLen2(5, n))
}
